import java.util.Scanner;

public class BigInt {
    // 内部类，表示双向链表的结点
    private class Node {
        int val;
        Node prev, next;

        Node(int val) {
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }

    private Node head, tail;

    public BigInt() {
        head = null;
        tail = null;
    }

    // 从字符串构造大整数
    public BigInt(String s) {
        head = null;
        tail = null;
        for (int i = s.length() - 1; i >= 0; i--) {
            int digit = s.charAt(i) - '0';
            Node node = new Node(digit);
            if (head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                node.prev = tail;
                tail = node;
            }
        }
    }

    // 大整数加法
    public BigInt add(BigInt other) {
        Node p = head, q = other.head;
        int carry = 0;
        BigInt result = new BigInt();
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = x + y + carry;
            int digit = sum % 10;
            carry = sum / 10;
            Node node = new Node(digit);
            if (result.head == null) {
                result.head = node;
                result.tail = node;
            } else {
                result.tail.next = node;
                node.prev = result.tail;
                result.tail = node;
            }
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry != 0) {
            Node node = new Node(carry);
            result.tail.next = node;
            node.prev = result.tail;
            result.tail = node;
        }
        return result;
    }

    // 大整数乘法
    public BigInt multiply(BigInt other) {
        Node p = head;
        BigInt result = new BigInt();
        int i = 0;
        while (p != null) {
            int carry = 0;
            Node q = other.head;
            BigInt temp = new BigInt();
            while (q != null) {
                int x = p.val;
                int y = q.val;
                int prod = x * y + carry;
                int digit = prod % 10;
                carry = prod / 10;
                Node node = new Node(digit);
                if (temp.head == null) {
                    temp.head = node;
                    temp.tail = node;
                } else {
                    temp.tail.next = node;
                    node.prev = temp.tail;
                    temp.tail = node;
                }
                q = q.next;
            }
            if (carry != 0) {
                Node node = new Node(carry);
                temp.tail.next = node;
                node.prev = temp.tail;
                temp.tail = node;
            }
            for (int j = 0; j < i; j++) {
                temp.head.prev = new Node(0);
                temp.head.prev.next = temp.head;
                temp.head = temp.head.prev;
            }
            i++;
            result = result.add(temp);
            p = p.next;
        }
        return result;
    }

    // 将大整数转换为字符串
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node p = tail;
        while (p != null) {
            sb.append(p.val);
            p = p.prev;
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请选择操作：");
        System.out.println("1. 大整数加法");
        System.out.println("2. 大整数乘法");
        int choice = scanner.nextInt();
        System.out.println("请输入第一个大整数：");
        String num1 = scanner.next();
        System.out.println("请输入第二个大整数：");
        String num2 = scanner.next();

        BigInt a = new BigInt(num1);
        BigInt b = new BigInt(num2);

        switch (choice) {
            case 1:
                System.out.println("加法结果：" + a.add(b));
                break;
            case 2:
                System.out.println("乘法结果：" + a.multiply(b));
                break;
            default:
                System.out.println("无效的选择");
        }
    }
}